# @Time    :2025/4/10 14:00
def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return  alist # 不再拆分

    mid = n // 2
    # left采用归并排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])
    # merge 是将两个有序的子序列 合并为一个新的整体
    # merge=(left,right)
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] <= right_li[right_pointer]:#如果左边的数小于右边的数，就把左边的书加入到列表result
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(merge_sort(alist))
    # sorted_li=merge_sort(alist)
    # print(sorted_li)
    print(alist)
    print(merge_sort([1, 2, 3,89, 5,16, 27, 18, 9, 10]))
    print(merge_sort([91, 12, 31, 4]))
